RSDP - Rahil's SemiDefinite Program solver

RSDP is a standalone semidefinite program (SDP) solver, that can multithread the
computation and use multiprecision data types. A large number of problems can be
written in terms of SDPs and SDPs can be solved relatively efficiently using
interior point methods. We note that SDPs subsume linear programming (LP), convex
quadratically constrained quadratic programming (QCQP), and second order cone
programming (SOCP) problems, however, solvers written specifically for such
problems are likely to be more efficient.

There are a number of free SDP solvers that already exist. I've personally used
CSDP (projects.coin-or.org/Csdp) and SDPA (sdpa.sourceforge.net) (both had several
annoying bugs and pretty unreadable source code). CSDP can multithread the
calculation and uses the data type "double" internally, which has a fixed small
size, so the accuracy of the solutions it returns is relatively low. SDPA can make
use of the the GNU Multiple Precision library (GMP) and so produce arbitrarily
accurate solutions but at the expense of being significantly slower. Also it
doesn't support multithreading together with multiprecision (you can have one or
the other). I needed a solver which made use of both multithreading and
multiprecision, and since I couldn't find one I decided to write my own. I should
point out that convex optimization is not my area of expertise so I don't really
know what I'm doing. However, the algorithm I've written seems to work and
hopefully others who are more proficient can build on it to make it more robust
and efficient.

RSDP uses OpenMP to multithread the computation, and uses GMP or the Boost library
to handle multiprecision. Although the Boost library is slower than GMP it is
easier to compile on a Windows operating system and so has been included in order
to make the application cross-platform. RSDP works in much the same way as CSDP
(see the CSDP manual). To run the solver we type at the console something that
looks like:

<executable> <problem file> <final solution> [<optional initial solution>]

E.g.
rsdp.exe prob1.dat-s prob1.out
./rsdp example2.dat-s example2.out example2.ini-s

Like CSDP we use SDPA's sparse input and output file format (see the SDPA manual).
There are a few differences between CSDP and RSDP, firstly RSDP always requires a
".out" file be specified to store the solution (in CSDP this is optional). RSDP
uses the ".out" filename to create temporary files (with the extensions ".tmp1"
and ".tmp2"). These temporary files store the current state of the solution in
case an external error occurs interrupting the calculation, for example a power
outage that crashes the computer. We create two temporary files just in case a
crash occurs whilst the program is in the middle of overwriting a temporary file.
Either temporary file can be used to restart the computation by specifiying it as
the "initial solution file". RSDP uses different parameters than CSDP, the default
parameters hard-coded in the program can be overridden by creating a "param.rsdp"
file, an example of such a file should be included with the program (it includes
an explanation of what the parameters are). Finally a typical iteration of RSDP is
displayed in the console as:

Time: 17:10  Iter: 76   Gap: 7.5e-15  Cons: 3.6e-51  DInfeas: +1.2e+00
Primal Obj: +2.749999999999965049675294378045e+00
Dual   Obj: +2.750000000000013980129882251518e+00

The "Time" parameter gives the time of day the iteration completed (useful when
trying to estimate how long the computation might take).

The "Iter" parameter gives the iteration number.

The "Gap" parameter gives the duality gap, a measure of how close the primal and
dual solutions are to each other.

The "Cons" parameter tells us to what tolerance the primal and dual constraints
are satisfied.

The "PInfeas" or "DInfeas" parameter indicates how close the solution is to being
able to show primal or dual infeasibility respectively (only the worst offender is
displayed).

The "Primal Obj" and "Dual Obj" parameters indicate the current primal and dual
objective values which should be converging towards each other. The dual value
should always upper bound the primal value assuming the primal and dual
constraints are precisely satisfied. However, since in general the constraints are
not precisely satisfied the primal value can sometimes become larger than the
dual. Consequently the "Gap" parameter is perhaps a more useful measure of how
close the primal and dual solutions are.

For the purposes of testing things out we include the file "prob.dat-s" taken from
the CSDP manual. RSDP should create a ".out" file that looks something like:

7.500000000000000000000000000006e-01 1.000000000000000000000000000000e+00
1 1 1 1 2.500000000000000000000000000018e-01
1 1 1 2 -2.499999999999999999999999999994e-01
1 1 2 2 2.500000000000000000000000000018e-01
1 2 1 1 8.757219548746914595199026411285e-31
1 2 1 3 2.919073182915638198399675470428e-31
1 2 2 2 2.000000000000000000000000000001e+00
1 2 3 3 2.000000000000000000000000000001e+00
1 3 1 1 7.500000000000000000000000000006e-01
1 3 2 2 1.000000000000000000000000000000e+00
2 1 1 1 1.250000000000000000000000000002e-01
2 1 1 2 1.249999999999999999999999999990e-01
2 1 2 2 1.250000000000000000000000000002e-01
2 2 1 1 6.666666666666666666666666666657e-01
2 2 1 3 -9.730243943052127327998918234674e-32
2 2 2 2 2.919073182915638198399675470403e-31
2 2 3 3 2.919073182915638198399675470402e-31
2 3 1 1 7.784195154441701862399134587736e-31
2 3 2 2 5.838146365831276396799350940813e-31

(Note that this is significantly more accurate than the solution given in the CSDP
manual.)